package mincostmaxflow;

import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Observable;
import java.util.Vector;
import java.util.logging.Level;
import java.util.logging.Logger;

class MinCostMaxFlow extends Observable implements Runnable{
    /**
     * initial graph structure
     */
    private Graph<Edge> graph;

    /**
     * This variable contains the most recent maximum flow achieved
     */
    private Graph<Edge> flowGraph;
//    private static Vector<Edge> incrementalGraph;

    /**
     * The incremental graph, using which we find the next cheapest path.
     * This is the one containing both straight and reversed edges.
     */
    private Graph<Edge> incrementalGraph;
//    private ArrayList<Integer> sources;
//    private ArrayList<Integer> drains;
    private int source;
    private int drain;

    GraphDisplayable mcgui;
//    static MinCostGUI mcgui;

    /**
     * Each element contains a route, through which the went the cheapest
     * flow as key and total cost of this step as value.
     */
    private Map<Route<Edge>, Integer> flow_increments;

    /**
     * Each element contains a graph, showing current total
     * flow as key and total cost of this step as value.
     */
    private Map<Graph<Edge>, Integer> overall_flow_increment_steps;

    public MinCostMaxFlow(Graph<Edge> gve){

	this.graph = adaptIfSeveralSourcesOrDrains(gve);
        /**
         * Each element contains a route, through which the went the cheapest
         * flow as key and total cost of this step as value.
         */
        flow_increments = new LinkedHashMap<Route<Edge>, Integer>();
	
        overall_flow_increment_steps = new LinkedHashMap<Graph<Edge>, Integer>();
	
        createFlowGraph();
        createIncrementalGraph();
    }
    
/*
    public void launch(Vector<Edge> g//,
//            ArrayList<Integer> srcs,
//            ArrayList<Integer> drns
	    )
            throws Exception{
//        this.sources = srcs;
//        this.drains = drns;

        graph = adaptIfSeveralSourcesOrDrains(new Graph(g));

        flow_increments = new LinkedHashMap<Route<Edge>, Integer>();

        overall_flow_increment_steps = new LinkedHashMap<Graph<Edge>, Integer>();

        createFlowGraph();
        createIncrementalGraph();
        performCalculation();
    }
*/

    private Graph<Edge> adaptIfSeveralSourcesOrDrains(Graph<Edge> g){
        Collection<Edge> temp;
        if(g.sourcesAmount() != 1){
//        if(this.sources.size() != 1){
            int min_vertex = getVertexWithExtremeNumber(g, false);
            min_vertex--;
//            for(Integer i : sources){
            for(Integer i : g.getSources()){
                temp = getAllEdgesFromVertex(g, i);
                int total_flow = 0;
                for(Edge e : temp){
                    total_flow += e.capacity_or_flow;
                }
                g.add(new Edge(min_vertex, i, 0,  total_flow));
            }
            this.source = min_vertex;
        }
        else{
	    this.source = g.getSources().get(0);
//            this.source = this.sources.get(0);
        }
//        if(this.drains.size() != 1){
        if(g.drainsAmount() != 1){
            int max_vertex = getVertexWithExtremeNumber(g, true);
            max_vertex++;
//            for(Integer i : drains){
            for(Integer i : g.getDrains()){
                temp = getAllEgdesToVertex(g, i);
                int total_flow = 0;
                for(Edge e : temp){
                    total_flow += e.capacity_or_flow;
                }
                g.add(new Edge(i, max_vertex, 0,  total_flow));
            }
            this.drain = max_vertex;
        }
        else{
//            this.drain = this.drains.get(0);
            this.drain = g.getDrains().get(0);
        }
        return g;
    }

    private void createFlowGraph(){
        flowGraph = new Graph<Edge>();
        for(Edge e : graph){
            flowGraph.add(new Edge(e.source, e.destination, 0, 0));
        }
    }

    private void createIncrementalGraph(){
//        incrementalGraph = new Vector<Edge>();
        incrementalGraph = new Graph<Edge>();
        Edge cur_flow;
        for(Edge e : graph){
            if((cur_flow = flowGraph.findEdge(e)) != null){
//            if((cur_flow = findEdge(flowGraph, e)) != null){
                if(cur_flow.capacity_or_flow < e.capacity_or_flow){
                    incrementalGraph.add(new Edge(e.source, e.destination, e.cost, e.capacity_or_flow, false));
                }
                if(cur_flow.capacity_or_flow > 0){
                    incrementalGraph.add(new Edge(e.destination, e.source, -1*e.cost, e.capacity_or_flow, true));
                }
            }
        }
    }
/*
    public Edge findEdge(Collection<Edge> g, Edge to_find){
        for(Edge e : g){
            if(e.equals(to_find))
                return e;
//
//            if(e.source == to_find.destination && e.destination == to_find.source)
//                return e;
//
        }
        return null;
    }
*/

    /**
     * Returns a number, of the vertex with maximum or minimum id
     * @param g Route or Graph where to search
     * @param max a switch. If it's true, searches for vertex with max number. Min number
     * if otherwise
     * @return a number, of the vertex with maximum or minimum id
     */
    public int getVertexWithExtremeNumber(Route<Edge> g, boolean max){
        int result = g.lastElement().source;
        if(max){
            for(Edge e : g){
                if(e.source > result)
                    result = e.source;
                if(e.destination > result)
                    result = e.destination;
            }
        }
        else{
            for(Edge e : g){
                if(e.source < result)
                    result = e.source;
                if(e.destination < result)
                    result = e.destination;
            }
        }
        return result;
    }

    public Collection<Edge> getAllEdgesFromVertex(Collection<Edge> g, int vertex){
        Graph<Edge> result = new Graph<Edge>();
        for(Edge e : g){
            if(e.source == vertex)
                result.add(new Edge(e.source, e.destination, e.cost, e.capacity_or_flow));
        }
        return result;
    }
    public Collection<Edge> getAllEgdesToVertex(Collection<Edge> g, int vertex){
        Graph<Edge> result = new Graph<Edge>();
        for(Edge e : g){
            if(e.destination == vertex)
                result.add(new Edge(e.source, e.destination, e.cost, e.capacity_or_flow));
        }
        return result;
    }

    /**
     * Gets maximum flow value which can be passed through given route.
     * @param path the route through which to calculate maximum flow value.
     * @return an integer containing maximum flow value
     * @throws Exception if something goes wrong
     */
    private int getMaximumPossibleFlow(Route<Edge> path)throws Exception{
        int flow_incr = Edge.INF;
        int capacity;
        Integer current_flow = null;
        for(Edge e : path){
            //TODO !!!!!
            capacity = incrementalGraph.findEdge(e).capacity_or_flow;
            if(e.isReverse){
                current_flow = flowGraph.findEdge(new Edge(e.destination, e.source, 0)).capacity_or_flow;
                if(flow_incr > capacity)
                    flow_incr = capacity;
            }
            else{
                current_flow = flowGraph.findEdge(e).capacity_or_flow;
                if(capacity-current_flow < flow_incr){
                   flow_incr = capacity-current_flow;
                }
            }
        }
        if(flow_incr == Edge.INF){
            throw new Exception("An error occured while calculating the flow increment");
        }
        System.out.println("\nThe flow'll be increased by " + flow_incr);
        return flow_incr;
    }

    /**
     * Updates the values in the flowGraph with data from parametres.
     * @param routeToUpdate contains edges to update
     * @param increment_value value for which the edges are updated.
     */
    private void updateFlowGraph(Route<Edge> routeToUpdate, int increment_value){
        for(Edge e : routeToUpdate){
            if(e.isReverse){
                flowGraph.findEdge(new Edge(e.destination, e.source, 0)).capacity_or_flow -= increment_value;
            }
            else
                flowGraph.findEdge(e).capacity_or_flow += increment_value;
        }
    }

    private void performCalculation() throws Exception{
//        Vector<Edge> currentCheapestPath = BellmanFord.bellmanFord(incrementalGraph,
//                source, drain);
        Route<Edge> currentCheapestPath = BellmanFord.bellmanFord(incrementalGraph,
                source, drain);
        while(currentCheapestPath != null){
            int flowIncrement = getMaximumPossibleFlow(currentCheapestPath);

	    //the current cheapest path
            updateFlowGraph(currentCheapestPath, flowIncrement);

            //separate steps that're performed
            int step_cost = 0;
            for(Edge e : currentCheapestPath){
                int cost = incrementalGraph.findEdge(e).cost;
                e.cost = cost;
                //int cur_flow = findEdge(flowGraph, e).capacity_or_flow;
                e.capacity_or_flow = flowIncrement;
                step_cost += cost * flowIncrement;
            }
            //Vector<Edge> total_actual_flow = new Vector<Edge>(flowGraph);

	    //Put a new Route, through which the cheapest flow is possible on current step
            Route<Edge> step_flow = new Route<Edge>(currentCheapestPath);
            flow_increments.put(step_flow, step_cost);

	    setChanged();
	    notifyObservers(step_flow);

	    setChanged();
	    notifyObservers(calculateCurrentActualFlow());

//            mcgui.showGraph(displayGraph(step_flow, ""), false);
//            mcgui.showGraph(displayGraph(calculateCurrentActualFlow(), ""), true);
            /*
            displayGraph(step_flow, "On this step flow went via:");
            System.out.println("The cost of this step: " + step_cost + "\n");
            displayGraph(calculateCurrentActualFlow(), "Current Flow on this step is:");
            System.out.println("Total cost of this step: " + current_overall_cost + "\n\n");
            */

            createIncrementalGraph();
            //displayGraph(incrementalGraph, "Incremental graph");
            currentCheapestPath = BellmanFord.bellmanFord(incrementalGraph, 
                source, drain);
        }
    }

    public int getCurrentOverallFlow(){
        int current_overall_flow = 0;
        for(Edge e : getAllEgdesToVertex(flowGraph, drain))
            current_overall_flow += e.capacity_or_flow;
        return current_overall_flow;
    }

    public int current_overall_cost;
    
    /**
     * generates and puts an updated copy of the flowsGraph to a special
     * Map overall_flow_increment_steps.
     * @return
     */
    public Graph<Edge> calculateCurrentActualFlow(){
        Graph<Edge> current_actual_flow = new Graph<Edge>();
        current_overall_cost = 0;
        for(Edge e : flowGraph){
            int cur_cost = e.capacity_or_flow * graph.findEdge(e).cost;
            current_actual_flow.add(new Edge(e.source,
                    e.destination,
                    graph.findEdge(e).cost,
                    e.capacity_or_flow));
//                e.cost = e.capacity_or_flow * findEdge(graph, e).cost;
            current_overall_cost += cur_cost;
            //current_overall_flow += e.capacity_or_flow;
        }
        overall_flow_increment_steps.put(current_actual_flow, current_overall_cost);
        return current_actual_flow;
    }

    public Graph<Edge> getGraph(String name) throws NoSuchFieldException,
            IllegalArgumentException,
            IllegalAccessException{
        Field f = MinCostMaxFlow.class.getDeclaredField(name);
        Graph<Edge> result = (Graph<Edge>) f.get(null);
        return result;
    }

    public String displayGraph(Graph<Edge> gr, String name){
        String result = new String();
        result += name + ": \n";
        System.out.println(name + ": ");
        for(Edge e : gr){
            result += e.toString()+"\n";
            System.out.println(e);
        }
        return result;
    }

    public void run() {
	try {
	    performCalculation();
	} catch (Exception ex) {
	    Logger.getLogger(MinCostMaxFlow.class.getName()).log(Level.SEVERE, null, ex);
	}
    }
/*
    public static void main(String[] args) throws Exception{
        Vector<Edge> temp = new Vector<Edge>();
        //
        
        temp.add(new Edge(1, 2, 31, 1));
        temp.add(new Edge(1, 3, 4, 10));
        temp.add(new Edge(2, 4, 31, 1));
        temp.add(new Edge(3, 4, 1, 10));
        temp.add(new Edge(3, 7, 30, 10));
        temp.add(new Edge(4, 5, 10, 10));
        temp.add(new Edge(5, 6, 31, 1));
        temp.add(new Edge(5, 7, 1, 10));
        temp.add(new Edge(6, 8, 31, 1));
        temp.add(new Edge(7, 8, 4, 10));
*/


/*
 *      Pavel Graph
        temp.add(new Edge(1, 4, 1, 10));
        temp.add(new Edge(1, 5, 4, 4));
        temp.add(new Edge(1, 6, 3, 2));
        temp.add(new Edge(2, 4, 7, 3));
        temp.add(new Edge(2, 7, 6, 7));
        temp.add(new Edge(3, 5, 2, 1));
        temp.add(new Edge(3, 8, 12, 5));
        temp.add(new Edge(4, 9, 1, 8));
        temp.add(new Edge(4, 5, 4, 8));
        temp.add(new Edge(5, 7, 5, 9));
        temp.add(new Edge(1, 6, 3, 2));
        temp.add(new Edge(6, 7, 6, 3));
        temp.add(new Edge(6, 11, 3, 6));
        temp.add(new Edge(7, 9, 4, 13));
        temp.add(new Edge(7, 10, 4, 6));
        temp.add(new Edge(7, 8, 1, 1));
        temp.add(new Edge(8, 10, 3, 10));
        temp.add(new Edge(8, 16, 8, 9));
        temp.add(new Edge(9, 11, 3, 3));
        temp.add(new Edge(9, 12, 2, 3));
        temp.add(new Edge(9, 14, 2, 9));
        temp.add(new Edge(10, 12, 6, 5));
        temp.add(new Edge(10, 16, 1, 2));
        temp.add(new Edge(11, 13, 5, 7));
        temp.add(new Edge(12, 14, 9, 2));
        temp.add(new Edge(12, 15, 7, 4));
*/
/*
        ArrayList<Integer> src, drn;
        src = new ArrayList<Integer>();
        src.add(1);
        drn = new ArrayList<Integer>();
        drn.add(8);

        MinCostMaxFlow.launch(temp, src, drn);

        int i = 1;

        for(Vector<Edge> GVE : overall_flow_increment_steps.keySet()){
            displayGraph(GVE, "Step "+i);
            System.out.println("Total cost to step " + i + " is " + overall_flow_increment_steps.get(GVE));
            i++;
        }
    }
*/
}
